package com.heima.arrayList01;

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
    1. ArrayList的添加过程
            Object[] elementData： ArrayList底层用来存储数据的对象数组。
        1. new ArrayList<>()底层会创建一个长度为0的空数组，赋值给elementData。
        2. 当调用集合的add添加元素方法时，方法内会先判断集合底层数组有没有存满：
            存满了：需要扩容，调用grow()方法对elementData数组进行扩容
        3. 将要添加的元素存入数组对应size的索引位置
        4. 将集合中的元素个数size + 1

    2. ArrayList的扩容机制
        1. 第一次添加，会将数组扩容为一个长度为10的新数组。
        2. 后续扩容，按照1.5倍的系数扩容。

        第一次：0-->10
        第二次：10-->15
        第三次：15-->22


    3. HashMap的添加过程
        1. 计算要添加元素的key的哈希值，拿着哈希值进行二次哈希无符号右移16位再取反：保证数据最大程度散列分布
        2. 添加之前先判断数组table是不是null或者长度是否为0，如果满足则resize扩容
        3. 计算元素的应存入索引位置：(数组长度 - 1) 二进制位与& hash值
        4. 判断该位置是否为null，是null则直接创建Node节点存入数组对应索引位置
        5. 如果不为null,则判断哈希值是否一致：如果不一致，则存入链表或者红黑树
        6. 如果哈希值一致，那么产生哈希冲突，触发equals比较：
        7. equals比较为true,认为是重复元素，那么会拿新存入的数据覆盖原有的数据。
        8. equals比较为false,认为是非重复元素，那么会往红黑树或者链表中追加。


    4. HashMap的扩容机制
        4.1 源码是通过resize()方法扩容，第一次扩容是在第一次往集合中添加元素时，因为table初始值为null,
                                    会触发扩容：将table数组扩容为长度16
        4.2 后续当往集合中添加时，元素个数 > 临界值（threshold）时，也会触发集合扩容，扩容会将table数组长度 * 2   16 --> 32  --> 64
                tips:   临界值：第一次取值是拿数组长度16 * 加载因子0.75得到的，也就是12
                                后续随着集合的扩容，会基于上一个临界值 * 2
        4.3 当链表中的节点个数 > 8时，会调用treeifyBin()尝试将链表树化，在树化之前会先判断数组table的长度是否小于64，
                如果小于64，这时候放弃树化，而是采用resize()扩容数组，分散链表压力

    5. HashMap中链表和红黑树的转换过程
         1. 链表转红黑树:     源码方法：replacementTreeNode()
                触发条件：    当数组长度 >= 64 并且 链表长度 > 8;

         2. 红黑树转链表:     源码方法：replacementNode()
                 a. 往集合中不断put导致数组扩容，扩容后，红黑树节点拆分，个数 <= 6 时，会将红黑树结构退化回链表结构。
                 b. 从集合中进行remove删除元素时，如果删除之前，红黑树结构中，根节点，根节点的左子节点，根节点的左孙子节点，
                    根节点的右子节点，这四个中任意一个为null，则会将红黑树结构退化回链表结构。
 */
public class Demo1 {
    public static void main(String[] args) throws Exception {
        //底层：哈希表结构 ： 数组 + 链表 + 红黑树
        HashMap<Student,String> map = new HashMap<>();

        for (int i = 1; i <= 11; i++) {
            map.put(new Student(),"aaaa");
        }

        map.remove(new Student());

        getLength(map);
        /**
         *  key1:    1
         *  i = (n - 1) & hash
         *    15 & 1
         *    15：     00001111
         * &   1：     10000001
         * --------------------------
         *             00000001
         *
         */
    }

    private static void getLength(HashMap<Student, String> map) throws NoSuchFieldException, IllegalAccessException {
        Class mapClazz = map.getClass();
        Field tableField = mapClazz.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] tableArray = (Object[]) tableField.get(map);
        System.out.println(tableArray.length);
    }
}
